#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e7 + 10;
int p[N], cnt; bool st[N];
LL phi[N];

void get_phi()
{
	int n = 1e7;
	phi[1] = 1;
	for(int i = 2; i <= n; i++)
	{
		if(!st[i]) 
		{
			p[++cnt] = i;
			phi[i] = i - 1;	
		}
		for(int j = 1; 1ll * i * p[j] <= n; j++)
		{
			int x = i * p[j];
			st[x] = true;
			if(i % p[j] == 0)
			{
				phi[x] = p[j] * phi[i]; 
				break;	
			}	
			else
			{
				phi[x] = (p[j] - 1) * phi[i]; 
			}
		}	
	}	
} 

LL qpow(LL a, LL b, LL p)
{
	LL ret = 1;
	while(b)
	{
		if(b & 1) ret = ret * a % p;
		b >>= 1;
		a = a * a % p;
	}
	return ret;
} 

int dfs(int p)
{
	if(p == 1) return 0;
	return qpow(2, dfs(phi[p]) + phi[p], p);
}

int main()
{
	get_phi();
//	for(int i = 1; i <= 10; i++) cout << phi[i] << " ";
	int T; cin >> T;
	while(T--)
	{
		int p; cin >> p;
		cout << dfs(p) << endl;
	}
	return 0;
}
